package everyday;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * @author zhangmin
 * @create 2022-04-28 10:05
 *
 * LRU需要记录K-V和记录顺序的list
 */
public class LRUCache {
    int capacity;
    HashMap<Integer,Integer> cache;
    LinkedList<Integer> list;

    public LRUCache(int capacity) {
        this.capacity=capacity;
        this.cache=new HashMap<>();
        this.list=new LinkedList<>();
    }

    public int get(int key) {
        //直接查找，如果存在，将这个key移动到最后
        if (cache.containsKey(key)) {
            makeRecently(key);
            return cache.get(key);
        }else {
            return -1;
        }
    }

    public void put(int key, int value) {
        //先判断这个key是否存在
        if (cache.containsKey(key)){
            cache.put(key,value);
            makeRecently(key);
        }else {
            //判断容量
            cache.put(key,value);
            list.addLast(key);
            while (cache.size()>capacity){
                int firstKey = list.removeFirst();
                cache.remove(firstKey);

            }
        }
    }

    public void makeRecently(int key){
        if (cache.containsKey(key)){
            list.remove((Integer) key);
            list.addLast(key);
        }
    }

    public static void main(String[] args) {
        LRUCache lruCache=new LRUCache(2);
        lruCache.put(1,1);
        lruCache.put(2,2);
        System.out.println(lruCache.get(1));
        lruCache.put(3,3);
        System.out.println(lruCache.get(2));
        lruCache.put(4,4);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));
    }
}
